/*
题目: 火柴拼正方形
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。
你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

https://leetcode.cn/problems/matchsticks-to-square
 */
public class Makesquare {
    public boolean makesquare(int[] matchsticks) {
        // 回溯法 : 桶有四个
        int sum = 0;
        for (int x : matchsticks)
            sum += x;

        if (sum % 4 != 0)   return false;
        sum /= 4;

        int[] bucket = new int[4];
        Arrays.fill(bucket, sum);
        // 排序后, 从大火柴开始放置, 为了让一边尽快饱和, 减少重复试错
        Arrays.sort(matchsticks);

        return backTrack(matchsticks, bucket, matchsticks.length - 1);
    }

    // 从最后一个下标开始回溯, 如果桶剩下的装不下第一个木柴, 就回
    private boolean backTrack(int[] nums, int[] bucket, int index) {
        if (index == -1) {
            return true;
        }

        for (int i = 0; i < 4; i++) {
            // 如果上一个桶的装法是错的, 这个桶也必然和上一个桶有一样的装法
            // 所以直接跳到下一个桶
            if (bucket[i] == 0 || i > 0 && bucket[i] == bucket[i - 1]) {
                continue ;
            }
            // 验证这个玩意能不能进入这个桶, 确保这个进入桶之后还有机会刚好满
            // 确保装进去之后恰好达到 0
            if (bucket[i] - nums[index] >= nums[0] || bucket[i] == nums[index]) {
                bucket[i] -= nums[index];
                if (backTrack(nums, bucket, index - 1)) {
                    return true;
                }
                bucket[i] += nums[index];
            }
        }

        return false;
    }
}
